#include <iostream>
using namespace std;

int search(int A[], int n, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(n==0)
        return -1;

    int left = 0;
    int right = n;
    while(left < right-1){
        int mid = (left + right)/2;
        if(A[mid] == target){
            return mid;
        }
        else{
            if(A[left] < A[right-1]){
                if(A[mid] < target){
                    left = mid+1;
                }
                else{
                    right = mid;
                }
            }
            else{
                if(A[mid] > A[left]){
                    if(A[left] <= target && target < A[mid]){
                        right = mid;
                    }
                    else{
                        left = mid+1;
                    }
                }
                else{
                    if(A[mid] < target && target <= A[right-1]){
                        left = mid+1;
                    }
                    else{
                        right = mid;
                    }
                }
                
            }
        }
    }
    if(A[left] == target){
        return left;
    }
    else{
        return -1;
    }
}



int main(){
    int A[] = {1,3};
    cout<<search(A, 2, 0);

    return 0;
}